import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //时间复杂度： O(logN)
    private void siftDown(int parent, int usedSize) {
        int child = 2*parent+1;
        //至少有左孩子
        while (child < usedSize) {
            //1.比较左右孩子最大值
            if(child+1 < usedSize && elem[child] < elem[child+1]) {
                child++;
            }
            //走到这里 child一定是左右孩子的最大值的下标
            if(elem[child] > elem[parent]) {
                swap(elem,parent,child);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                minHeap.offer(arr[i]);
                //siftDown(0,k);
            }else{
                if (arr[i] < minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(arr[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }


    //堆删除结点
    public void poll() {
        if (isEmpty()) {
            return;
        }
        swap(elem,0,elem.length - 1);
        usedSize--;
        siftDown(0,usedSize);
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }


    public int[] findMin(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //创建小根堆
        for (int i = 0; i < array.length; i++) {
            minHeap.offer(array[i]);
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    //设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
    /*public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                minHeap.offer(arr[i]);
                //siftDown(0,k);
            }else{
                if (arr[i] < minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(arr[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }*/


}


class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k <= 0){
            return new int[0];
        }
        IntCmp intCmp = new IntCmp();
        PriorityQueue<Integer> q = new PriorityQueue<>(k,intCmp);
        for(int i = 0; i < arr.length; ++i){
            // 先使arr中前k个元素创建小堆
            if(i < k){
                q.offer(arr[i]);
            }else{
                // 使用堆顶与arr中剩余元素进行比较，如果arr[i]小于堆顶元素时，则替换堆顶元素
                if(intCmp.compare(arr[i], q.peek()) > 0){
                    q.poll();
                    q.offer(arr[i]);
                }
            }
        }
        // 堆中剩余的n个元素就是所要的k个元素
        int[] ret = new int[k];
        for(int i = 0; i < k; ++i){
            ret[i] = q.poll();
        }
        return ret;
    }
}
